#include <stdio.h>
#include <stdlib.h>
#include <math.h>

float func(int n,float *cityX,float *cityY,int *rank,char **cityName){
	float t = 0;
	int i,r,s;
	for(i = 0;i < n-1;i++){
		r = rank[i];
		s = rank[i + 1];
		t += sqrtf((cityX[s]-cityX[r])*(cityX[s]-cityX[r])+(cityY[s]-cityY[r])*(cityY[s]-cityY[r]));
	}
	r = rank[0];
	s = rank[n-1];
	t += sqrtf((cityX[s]-cityX[r])*(cityX[s]-cityX[r])+(cityY[s]-cityY[r])*(cityY[s]-cityY[r]));
	return t;
}

void exchange(int a,int b,int *rank){
	int t = rank[a]; rank[a] = rank[b]; rank[b] = t;
}

int main(int arc,char **argv){
	int n,i,a,b;
	FILE *read = fopen(argv[1],"r");
	FILE *write = fopen(argv[2],"w");
	fscanf(read,"%d",&n);
	char **cityName = malloc(sizeof(char*)*n);
	float *cityX = malloc(sizeof(float)*n);
	float *cityY = malloc(sizeof(float)*n);
	float funcI,funcJ,p,funcK = 0;
	int *rank = malloc(sizeof(int)*n);
	for(i = 0;i < n;i++){
		cityName[i] = malloc(sizeof(char)*10);
		fscanf(read,"%s\t%f\t%f\n",cityName[i],&cityX[i],&cityY[i]);
		rank[i] = i;
	}
	
	float t = 280.0; ///初始温度为280度
	float c = 0.98; ///降温算法的系数
	funcI = func(n,cityX,cityY,rank,cityName);
	while(funcK != funcI) { ///算法结束的条件，即，相邻的温度所得到的结果相同
		funcK = funcI;
		for(i = 0;i < 400 * n;i++){ ///同一温度内计算结束的条件，连续迭代运算400*n，n为城市的数目。
			do{	
				a = rand()%n; 
				b = rand()%n;
			}while (a == b);
			exchange(a,b,rank);
			funcJ = func(n,cityX,cityY,rank,cityName);
			if(funcJ < funcI) ///如果此次运算得到的结果比上次运算得到的结果要低，则此次结果被接受
				funcI = funcJ;
			else{
				p = expf((funcI-funcJ)/t);	///指标函数
				if(p > ((double)rand())/RAND_MAX)	///如果指标函数的结果大于一个随机百分数，则可以接受。
					funcI = funcJ;
				else 	///否则，保留原来的结果
					exchange(b,a,rank);
			}
		}
		t = c * t; ///降温过程
		for(i = 0;i < n;i++)
			fprintf(write,"%s ",cityName[rank[i]]);
		fprintf(write,"%f\n",funcI);			
	}
	return 0;
}
